/*
 * Copyright (c) 2007 by L. Paul Chew.
 *
 * Permission is hereby granted, without written agreement and without
 * license or royalty fees, to use, copy, modify, and distribute this
 * software and its documentation for any purpose, subject to the following
 * conditions:
 *
 * The above copyright notice and this permission notice shall be included
 * in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
 */

import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * A Triangle is an immutable Set of exactly three Pnts.
 * 
 * All Set operations are available. Individual vertices can be accessed via
 * iterator() and also via triangle.get(index).
 * 
 * Note that, even if two triangles have the same vertex set, they are
 * *different* triangles. Methods equals() and hashCode() are consistent with
 * this rule.
 * 
 * @author Paul Chew
 * 
 *         Created December 2007. Replaced general simplices with geometric
 *         triangle.
 * 
 */
public class Triangle extends ArraySet<Point> {

	private int idNumber; // The id number
	@SuppressWarnings("unused")
	private Point circumcenter = null; // The triangle's circumcenter

	private static int idGenerator = 0; // Used to create id numbers
	public static boolean moreInfo = false; // True iff more info in toString
	private Point[] order = null;

	/**
	 * @param vertices
	 *            the vertices of the Triangle.
	 * @throws IllegalArgumentException
	 *             if there are not three distinct vertices
	 */
	public Triangle(Point... vertices) {
		this(Arrays.asList(vertices));
		for (int i = 0; i < vertices.length; i++) {
			vertices[i].addTriangle(this);
		}
	}

	/**
	 * @param collection
	 *            a Collection holding the Simplex vertices
	 * @throws IllegalArgumentException
	 *             if there are not three distinct vertices
	 */
	public Triangle(Collection<? extends Point> collection) {
		super(collection);
		idNumber = idGenerator++;
		if (this.size() != 3)
			throw new IllegalArgumentException(
					"Triangle must have 3 vertices and not " + this.size());
		Iterator<? extends Point> it = collection.iterator();
		while (it.hasNext()) {
			it.next().addTriangle(this);
		}
	}

	@Override
	public String toString() {
		if (!moreInfo)
			return "Triangle" + idNumber;
		return "Triangle" + idNumber + super.toString();
	}

	/**
	 * Get arbitrary vertex of this triangle, but not any of the bad vertices.
	 * 
	 * @param badVertices
	 *            one or more bad vertices
	 * @return a vertex of this triangle, but not one of the bad vertices
	 * @throws NoSuchElementException
	 *             if no vertex found
	 */
	public Point getVertexButNot(Point... badVertices) {
		Collection<Point> bad = Arrays.asList(badVertices);
		for (Point v : this)
			if (!bad.contains(v))
				return v;
		throw new NoSuchElementException("No vertex found");
	}

	/**
	 * True iff triangles are neighbors. Two triangles are neighbors if they
	 * share a facet.
	 * 
	 * @param triangle
	 *            the other Triangle
	 * @return true iff this Triangle is a neighbor of triangle
	 */
	public boolean isNeighbor(Triangle triangle) {
		int count = 0;
		for (Point vertex : this)
			if (!triangle.contains(vertex))
				count++;
		return count == 1;
	}

	/**
	 * Report the facet opposite vertex.
	 * 
	 * @param vertex
	 *            a vertex of this Triangle
	 * @return the facet opposite vertex
	 * @throws IllegalArgumentException
	 *             if the vertex is not in triangle
	 */
	public ArraySet<Point> facetOpposite(Point vertex) {
		ArraySet<Point> facet = new ArraySet<Point>(this);
		if (!facet.remove(vertex))
			throw new IllegalArgumentException("Vertex not in triangle");
		return facet;
	}

	/**
	 * @return the triangle's circumcenter
	 */
	public Point getCircumcenter() {
//		if (circumcenter == null)
//			circumcenter = Point.circumcenter(this.toArray(new Point[0]));
//		return circumcenter;
		return Point.circumcenter(this.toArray(new Point[0]));
	}

	/* The following two methods ensure that a Triangle is immutable */

	@Override
	public boolean add(Point vertex) {
		throw new UnsupportedOperationException();
	}

	@Override
	public Iterator<Point> iterator() {
		return new Iterator<Point>() {
			private Iterator<Point> it = Triangle.super.iterator();

			public boolean hasNext() {
				return it.hasNext();
			}

			public Point next() {
				return it.next();
			}

			public void remove() {
				throw new UnsupportedOperationException();
			}
		};
	}

	private Point[] sortTriangle() {
		order = this.toArray(new Point[0]);
		order[0] = get(0);
		for (int i = 1; i < 3; i++) {
			if (order[0].getY() >= order[i].getY()) {
				Point tmp = order[0];
				order[0] = order[i];
				order[i] = tmp;
			}
		}
//		if (order[0].polarCmp(order[1], order[2]) == 1) {
//			Point tmp = order[1];
//			order[1] = order[2];
//			order[2] = tmp;
//		}
		Arrays.sort(order,1,order.length,order[0].comparator());
		return order;
	}

	public Point getSorted(int i) {
		if (i > 3)
			return null;
		if (order == null)
			sortTriangle();
		return order[i];
	}
	
	public Point getNextInCCW(Point point){
		if(!contains(point))
			return null;
		if (order == null)
			sortTriangle();
		for(int i = 0;i<order.length;i++){
			if(order[i]==point)
				return order[(i+1)%3];
		}
		return null;
	}

	/* The following two methods ensure that all triangles are different. */

	@Override
	public int hashCode() {
		return (int) (idNumber ^ (idNumber >>> 32));
	}

	@Override
	public boolean equals(Object o) {
		return (this == o);
	}

	public boolean hasSameVertices(Triangle triangle) {
		// System.out.println("******************\n"+this+"\n"+triangle);
		// System.out.println(contains(triangle.get(0)) &&
		// contains(triangle.get(1)) && contains(triangle.get(2))) ;
		return (contains(triangle.get(0)) && contains(triangle.get(1)) && contains(triangle
				.get(2)));
	}

	public void setReferencesToPoints() {
		for (Point point : this) {
			point.addTriangle(this);
		}
	}

	public void removeReferencesToPoints() {
		for (Point point : this) {
			point.removeTriangle(this);
		}
	}
	
	public boolean containsPointInside(Point point){
		this.sortTriangle();
		int first = isOnLeft(point,order[0],order[1]);
		int second = isOnLeft(point,order[1],order[2]);
		int third = isOnLeft(point,order[2],order[0]);
		return first!=-1 && second!=-1 && third!=-1;
	}
	
	public int[] getRelations(Point point){
		this.sortTriangle();
		int[] tmp = new int[3];
		tmp[0] = isOnLeft(point,order[0],order[1]);
		tmp[1] = isOnLeft(point,order[1],order[2]);
		tmp[2] = isOnLeft(point,order[2],order[0]);
		return tmp;
	}
	
	private int isOnLeft(Point t, Point a, Point b) {
		// returns 1 if t is on the left of the line from a to b
		double area = a.getX() * b.getY() - a.getY() * b.getX() + a.getY() * t.getX() -
		a.getX() * t.getY() + b.getX() * t.getY() - t.getX() * b.getY();
		if (area > 0)
		      return 1;
		    else if (area == 0)
		      return 0;
		    else
		      return -1;

	}
}